package com.example.demo.leetcode.classics150;

import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _142三角形最小路径和
 * @description
 * @date 2023/08/27 10:28
 * <p>
 * ******************************************************
 */
public class _142三角形最小路径和 {

    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][triangle.size()];
        dp[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> curr = triangle.get(i);
            List<Integer> last = triangle.get(i - 1);
            for (int j = 0; j < curr.size(); j++) {
                int item = curr.get(j);
                int a = item;
                int b = item;
                if (j - 1 < 0) {
                    a += dp[i - 1][j];
                } else {
                    a += dp[i - 1][j - 1];
                }
                if (j < last.size()) {
                    b += dp[i - 1][j];
                } else {
                    b += dp[i - 1][j - 1];
                }
                dp[i][j] = Math.min(a, b);
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i : dp[triangle.size() - 1]) {
            res = Math.min(res, i);
        }
        return res;
    }


}
